#include <stdio.h>
#include <stdlib.h>
void QuickSort(int a[],int low,int high){
    if(low>high)
        return;
    int x=a[low];
    int i=low+1,j=high,t;
    while(i<j) {
        while (i < high && a[i] < x)
            i++;
        while (j > low && a[j] > x)
            j--;
        if (i < j) {
            t = a[i];
            a[i] = a[j];
            a[j] = t;
        }
    }
    t=a[low];
    a[low]=a[j];
    a[j]=t;
    QuickSort(a,low,j-1);
    QuickSort(a,j+1,high);
}
void PopSort(int a[],int n){
    int i,j,t,tag;
    for(i=0;i<n-1;i++) {
        tag = 0;
        for (j = n - 1; j > i; j--) {
            if (a[j] < a[j - 1]) {
                t = a[j];
                a[j] = a[j - 1];
                a[j - 1] = t;
                tag = 1;
            }
        }
        if(!tag)
            break;
    }
}
void InsertSort(int a[],int n){
    int i,j,x;
    for(i=1;i<n;i++){
        x=a[i];
        for(j=i-1;j>-1&&a[j]>x;a[j+1]=a[j],j--);
        a[j+1]=x;
    }
}
void SelectedSort(int a[],int n){
    int i,j,t,kmin;
    for(i=0;i<n-1;i++){
        kmin=i;
        for(j=i+1;j<n;j++){
            if(a[j]<a[kmin]){
                kmin=j;
            }
        }
        if(a[i]-a[kmin]){
            t=a[i];
            a[i]=a[kmin];
            a[kmin]=t;
        }
    }
}
void Merge(int a[],int start,int end)
{
    int mid=(start+end)/2;
    int b[end-start];
    int i,j,k;
    i=start;
    j=mid;
    k=0;
    while(i<mid||j<end)
    {
        if(j==end||i<mid&&a[i]<a[j])
            b[k++]=a[i++];
        else
            b[k++]=a[j++];
    }
    for(i=start,j=0;j<k;)
        a[i++]=b[j++];
}

void MergeSort(int a[],int left,int right)
{
    if(right-left>1)
    {
        int mid=(right+left)/2;
        MergeSort(a,left,mid);
        MergeSort(a,mid,right);
        Merge(a,left,right);
    }
}
void AdjustHeap(int a[],int n){
    int end=n,tag;
    do{
        int pa=end/2,temp;
        tag=0;
        while(pa>0){
            if(a[pa]<a[pa*2]){
                temp=a[pa];
                a[pa]=a[pa*2];
                a[pa*2]=temp;
                tag=1;
            }
            if((pa*2+1)<=end&&a[pa]<a[pa*2+1]){
                temp=a[pa];
                a[pa]=a[pa*2+1];
                a[pa*2+1]=temp;
                tag=1;
            }
            pa--;
        }
    }while(tag);
}
void HeapSort(int a[],int n){
    while(n>1){
        AdjustHeap(a,n);
        int temp=a[1];
        a[1]=a[n];
        a[n]=temp;
        n--;
    }
}
void Print(int a[],int n){
    for(int i=0;i<n;i++)
        printf("%d\n",a[i]);
}
int main(void){
    int a[8]={2,1,4,8,3,8,5,6};
    //QuickSort(a,0,7);
    //PopSort(a,8);
    //InsertSort(a,8);
    //SelectedSort(a,8);
    //MergeSort(a,0,7);
    //HeapSort(a,8);//堆排序要浪费下标为0的单元，所以一定要浪费第一个，所以不对第一个排序。
    Print(a,8);
}